package arithmetic_40;

/**
 *
 * @author wxh
 */
public class Solution_9 {

	public int minDistance(String word1, String word2) {

		int n = word1.length();
		int m = word2.length();

		// 如果有一个字符串为空串
		if (n * m == 0) {
			return n + m;
		}

		// DP数组：一维表示单词1所在的字符位置i，二维表示单词2所在的字符位置j
		// 值表示：word1的前i个字符替换到word2前j个字符，最少需要多少操作步数
		int[][] dp = new int[n + 1][m + 1];


		// 边界状态初始化
		for (int i = 0; i < n + 1; i++) {
			dp[i][0] = i;
		}
		for (int j = 0; j < m + 1; j++) {
			dp[0][j] = j;
		}

		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < m + 1; j++) {
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) { // 如果两个字符相等
					dp[i][j] = dp[i-1][j-1];
				} else { //
					dp[i][j] = 1 + Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
				}
			}
		}

		return dp[n][m];

	}

}